#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>

using namespace std;

struct node
{
	int	val,dist;
	node	*l,*r;
	node() { val=dist=0; l=r=0; }
}U[310000];

int	ALL=0;
node *	ALLOC() { memset(U+(++ALL),0,sizeof(node)); return U+ALL; }

struct UnionHeap
{
	node	*root;

	UnionHeap() { root=0; }
	node*	Union(UnionHeap& temp) { return root=Union(root,temp.root); }
	int	top() { return root->val; }
	void	pop() { UnionHeap A,B; A.root=root->l; B.root=root->r; A.Union(B); root=A.root; }
	void	insert(const int x)
	{
		UnionHeap	A;
		A.init(x);
		Union(A);
	}

	void	init(const int d)
	{
		root=ALLOC();
		root->val=d;
		root->dist=0;
	}

	node*	Union(node * t1,node * t2)
	{
		if(!t1)return t2;
		if(!t2)return t1;
		if(t2->val > t1->val)swap(t1,t2);
		t1->r=Union(t1->r,t2);
		if((t1->r?t1->r->dist:-1) > (t1->l?t1->l->dist:-1))
			swap(t1->l,t1->r);
		if(!t1->r)t1->dist=0;
		else	t1->dist=t1->r->dist+1;
		return t1;
	}
}H[110000];

int	n,f[110000];

int	get_anc(const int x) { return f[x]==x ? x:f[x]=get_anc(f[x]); }
void	Union(const int x,const int y) { int	S=get_anc(x),T=get_anc(y); if(S!=T)f[T]=S; return ; }

int main()
{
	int	i,x,y,T;
	while(~scanf("%d",&n))
	{
		ALL=0;
		memset(H,0,sizeof(H));
		for(i=1;i<=n;++i)
		{
			scanf("%d",&x);
			H[i].init(x);
			f[i]=i;
		}
		scanf("%d",&T);
		while(T--)
		{
			scanf("%d%d",&x,&y);
			int	s=get_anc(x),t=get_anc(y);
			if(s==t)
			{
				printf("-1\n");
				continue;
			}
			H[s].insert(H[s].top()/2);
			H[s].pop();
			H[t].insert(H[t].top()/2);
			H[t].pop();
			H[s].Union(H[t]);
			printf("%d\n",H[s].top());
			Union(x,y);
		}
	}

	return 0;
}
